The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
Computing devices perform a variety of computations, including, without limitation, mapping and lookup operations, in which a relatively equal distribution of an input value across a number space is ideal. For instance, a hash function is any function that can be used to map data of potentially arbitrary size to data of fixed size. The mapped data, or a selected portion thereof, is said to be a hash “key.” This key is provided as input to the hash function, which then calculates an output value based on the key. The output values returned by a hash function are called hash values, or simply hashes. For a number of applications, the hash function must be deterministic—meaning that for a given input value it must always generate the same hash value. The hash function provides a mapping from one number space (or input value space) to another number space (or output value space) that is typically smaller than input value space.
A hash value returned from a hash function may be utilized in a variety of computing operations, termed herein as “hash-based operations.” For example, a hash table, or hash map, is a data structure used to implement an associative array, which is a structure that maps keys to values. The hash table may be, for example, an array of buckets or slots. A hash function is utilized to compute, for a given key, an index (i.e. the hash value) into the hash table, from which a value associated with that key can be retrieved.
Ideally, the hash function will assign each key to a unique bucket, but it is possible in some embodiments that two keys will generate an identical hash, causing both keys to point to the same bucket. Most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.
In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, hash tables are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets. For instance, in networking devices, information associated with a network packet may be determined using a hash table. Various portions or fields of the packet are extracted to form a key, and this key is entered into a hash function. The resulting hash value is used to locate an index within the table at which the information associated with the packet is stored. The associated information may include, for example and without limitation, an assigned data flow, selected path, storage address, applicable policy, and/or any other suitable values.
Hash functions serve yet many other purposes within computing devices, such as cryptography operations and data validation operations. Unless otherwise indicated, the techniques described herein may be utilized with respect to hash functions and other functions in any suitable computing context.